package com.yanceysong.codetop.s51_s60;

import com.yanceysong.common.TreeNode;

import java.util.HashMap;
import java.util.Map;
import java.util.ArrayDeque;
import java.util.Queue;


public class S57_Mid_105_从前序与中序遍历序列构造二叉树 {
    // value -> index 的映射，帮助 O(1) 在中序数组里定位根的位置
    private Map<Integer, Integer> inorderValueToIndex;

    /**
     * .<p>
     * .LeetCode 链接：<a href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/">...</a>
     * .<p>
     * .=============================== 题目描述 ===============================
     * .给定两个整数数组 preorder 和 inorder ，其中：
     * .- preorder 记录二叉树的 先序遍历 （根 → 左 → 右）
     * .- inorder 记录二叉树的 中序遍历 （左 → 根 → 右）
     * .请你 构造 该二叉树并返回它的根节点。
     * .已知：树中每个值互不相同（无重复值）。
     * .<p>
     * .=============================== 示例 ===============================
     * .示例 1：
     * .preorder = [3, 9, 20, 15, 7]
     * .inorder  = [9, 3, 15, 20, 7]
     * .输出：根节点 (值=3) ，其结构为：
     * .           3
     * .         /   \
     * .        9     20
     * .             /  \
     * .            15   7
     * .解释：先序第一个元素 3 是根；在中序里 3 左边是 [9] → 左子树，中序里 3 右边是 [15,20,7] → 右子树。
     * .<p>
     * .示例 2：
     * .preorder = [1]
     * .inorder  = [1]
     * .输出：单节点树（根=1）。
     * .<p>
     * .=============================== 核心标签 ===============================
     * .树 / 二叉树 / 递归 / 分治 / 哈希表 (索引映射) / 数组区间 / 构造问题
     * .<p>
     * .=============================== 关键洞察 ===============================
     * .1. 先序遍历的第一个元素总是 当前子树的根。
     * .2. 在中序遍历序列中定位该根的位置，左边区间就是整棵左子树的中序序列，右边区间就是整棵右子树的中序序列。
     * .3. 知道左子树的节点数量，就能在先序数组中“切片”出左子树的先序部分与右子树的先序部分。
     * .4. 递归重复上述过程即可完全还原树结构。
     * .5. 为了 O(1) 快速定位根在中序的位置，需要一个 哈希表：value -> index。
     * .<p>
     * .=============================== 为什么必须用哈希表？ ===============================
     * .如果每次根节点要 在线性扫描 中序数组找位置，会导致最坏 O(n^2)（退化链状树）。
     * .使用映射后，每一层递归定位根只需 O(1)，总时间 O(n)。
     * .<p>
     * .=============================== 递归设计（分治） ===============================
     * .函数目标：build(preL, preR, inL, inR) —— 构建“当前区间”代表的子树。
     * .参数含义：
     * .- preL, preR：先序数组的闭区间 [preL, preR]
     * .- inL,  inR ：中序数组的闭区间 [inL,  inR]
     * .步骤：
     * .1. 终止条件：preL > preR 时，区间为空，返回 null。
     * .2. 取根值 rootVal = preorder[preL]。
     * .3. 在中序中查 rootIndex = map[rootVal]。
     * .4. 左子树节点数量 leftSize = rootIndex - inL。
     * .5. 划分区间：
     * .   左子树先序：[preL+1, preL+leftSize]
     * .   左子树中序：[inL, rootIndex-1]
     * .   右子树先序：[preL+leftSize+1, preR]
     * .   右子树中序：[rootIndex+1, inR]
     * .6. 递归构造左右孩子，连接返回根。
     * .<p>
     * .=============================== ASCII 图（示例1构造过程） ===============================
     * .preorder = [3, 9, 20, 15, 7]
     * .inorder  = [9, 3, 15, 20, 7]
     * .第一次：root=3
     * .inorder 切分: [9] | 3 | [15,20,7]
     * .leftSize = 1
     * .┌ 构造左：pre[1,1], in[0,0] → 单节点 9
     * .└ 构造右：pre[2,4], in[2,4]
     * .  第二次（右子树）root=20
     * .  inorder 切分: [15] | 20 | [7]
     * .  leftSize=1
     * .  ┌ 左：pre[3,3], in[2,2] → 15
     * .  └ 右：pre[4,4], in[4,4] → 7
     * .得到：
     * .           3
     * .         /   \
     * .        9     20
     * .             /  \
     * .            15   7
     * .<p>
     * .=============================== 复杂度分析 ===============================
     * .时间复杂度：O(n) —— 每个节点只被访问 & 构造一次，哈希查找 O(1)。
     * .空间复杂度：O(n) —— 递归栈最坏深度 O(n)（链状树） + 哈希表 O(n)。
     * .<p>
     * .=============================== 典型边界情况 ===============================
     * .1. 空数组：返回 null。
     * .2. 单节点：左右递归立即命中终止条件。
     * .3. 完全不平衡（链状）：递归深度 n，但逻辑不变。
     * .4. 完全二叉树：左右区间均匀分裂。
     * .<p>
     * .=============================== 验证技巧 ===============================
     * .可以打印构造结果的：
     * .- 先序遍历（应与输入 preorder 一致）
     * .- 中序遍历（应与输入 inorder 一致）
     * .- 层序遍历（观察结构）
     * .<p>
     * .=============================== 总结 ===============================
     * .分治核心：利用“根在先序首位 + 中序左右分区”确定子树边界；辅以哈希表定位，递归切片构造。
     * <p>
     * .递归构造函数（分治核心）。
     * .@param preorder 先序数组
     * .@param inorder  中序数组
     * .@param preL 当前子树先序起始索引
     * .@param preR 当前子树先序结束索引
     * .@param inL  当前子树中序起始索引
     * .@param inR  当前子树中序结束索引
     * .@return 构造好的当前子树根节点
     */
    public TreeNode buildByRange(int[] preorder, int[] inorder,
                                 int preL, int preR,
                                 int inL, int inR) {
        // 终止条件：先序区间为空
        if (preL > preR) {
            return null;
        }
        // 1. 根节点值：先序区间第一个元素
        int rootVal = preorder[preL];
        // 2. 在中序数组中查找根的位置
        int rootIndexInInorder = inorderValueToIndex.get(rootVal);
        // 3. 左子树节点数量（用于切片先序数组）
        int leftSize = rootIndexInInorder - inL;
        // 4. 构造根节点
        TreeNode root = new TreeNode(rootVal);
        // 5. 递归构造左子树：先序 [preL+1, preL+leftSize]；中序 [inL, rootIndexInInorder-1]
        root.left = buildByRange(preorder, inorder,
                preL + 1, preL + leftSize,
                inL, rootIndexInInorder - 1);
        // 6. 递归构造右子树：先序 [preL+leftSize+1, preR]；中序 [rootIndexInInorder+1, inR]
        root.right = buildByRange(preorder, inorder,
                preL + leftSize + 1, preR,
                rootIndexInInorder + 1, inR);
        return root;
    }

    /**
     * .对外暴露的构造入口。
     * .完成：1. 边界处理 2. 构建中序索引映射 3. 调用递归。
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length == 0) {
            return null; // 空树
        }
        int n = preorder.length;
        // 构建哈希映射，加速根索引定位
        inorderValueToIndex = new HashMap<>(n * 2);
        for (int i = 0; i < n; i++) {
            inorderValueToIndex.put(inorder[i], i);
        }
        return buildByRange(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    // ======================== 以下为测试 & 辅助打印 ========================

    /**
     * .先序遍历（根-左-右）
     */
    private static void preorderPrint(TreeNode root, StringBuilder sb) {
        if (root == null) {
            return;
        }
        sb.append(root.val).append(' ');
        preorderPrint(root.left, sb);
        preorderPrint(root.right, sb);
    }

    /**
     * .中序遍历（左-根-右）
     */
    private static void inorderPrint(TreeNode root, StringBuilder sb) {
        if (root == null) {
            return;
        }
        inorderPrint(root.left, sb);
        sb.append(root.val).append(' ');
        inorderPrint(root.right, sb);
    }

    /**
     * .层序遍历：便于肉眼观察结构（null 省略）
     */
    private static String levelOrder(TreeNode root) {
        if (root == null) return "<empty>";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                sb.append(node.val).append(' ');
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            sb.append('|'); // 层分隔
        }
        return sb.toString();
    }

    // 验证：两个遍历结果是否与原输入数组一致
    private static boolean arraysMatch(int[] arr, String traversal) {
        String[] parts = traversal.trim().split("\\s+");
        if (arr.length != parts.length) return false;
        for (int i = 0; i < arr.length; i++) {
            if (!Integer.toString(arr[i]).equals(parts[i])) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        S57_Mid_105_从前序与中序遍历序列构造二叉树 solution = new S57_Mid_105_从前序与中序遍历序列构造二叉树();
        System.out.println("=== 从前序与中序构造二叉树 测试开始 ===\n");

        // 测试1：题目示例
        int[] preorder1 = {3, 9, 20, 15, 7};
        int[] inorder1 = {9, 3, 15, 20, 7};
        testCase(solution, preorder1, inorder1, "示例1：一般二叉树");

        // 测试2：单节点
        int[] preorder2 = {1};
        int[] inorder2 = {1};
        testCase(solution, preorder2, inorder2, "示例2：单节点");

        // 测试3：全左链（退化成链表） 形状：1<-2<-3  (根=1，右为空，左不断延伸)
        int[] preorder3 = {1, 2, 3};
        int[] inorder3 = {3, 2, 1};
        testCase(solution, preorder3, inorder3, "退化结构：全左链");

        // 测试4：全右链 形状：1->2->3
        int[] preorder4 = {1, 2, 3};
        int[] inorder4 = {1, 2, 3};
        testCase(solution, preorder4, inorder4, "退化结构：全右链");

        // 测试5：完全二叉树（满二叉树）
        // 构造：       1
        //           /   \
        //          2     3
        //         / \   / \
        //        4  5 6   7
        int[] preorder5 = {1, 2, 4, 5, 3, 6, 7};
        int[] inorder5 = {4, 2, 5, 1, 6, 3, 7};
        testCase(solution, preorder5, inorder5, "完全二叉树：满树");

        // 测试6：空树
        int[] preorder6 = {};
        int[] inorder6 = {};
        TreeNode root6 = solution.buildTree(preorder6, inorder6);
        assert root6 == null : "空数组应该返回 null";
        System.out.println("[空树] levelOrder = " + levelOrder(root6) + " (期望: <empty>)");
        System.out.println("✓ 空树测试通过\n");

        System.out.println("=== 所有测试完成 ===");
    }

    private static void testCase(S57_Mid_105_从前序与中序遍历序列构造二叉树 solution,
                                 int[] preorder, int[] inorder, String title) {
        System.out.println("--- " + title + " ---");
        TreeNode root = solution.buildTree(preorder, inorder);
        StringBuilder preSb = new StringBuilder();
        preorderPrint(root, preSb);
        StringBuilder inSb = new StringBuilder();
        inorderPrint(root, inSb);
        String level = levelOrder(root);
        System.out.println("输入 preorder = " + arrayToStr(preorder));
        System.out.println("输入 inorder  = " + arrayToStr(inorder));
        System.out.println("构造后 先序   = " + preSb);
        System.out.println("构造后 中序   = " + inSb);
        System.out.println("层序结构表示  = " + level);
        assert arraysMatch(preorder, preSb.toString()) : "先序遍历不匹配，构造可能有误";
        assert arraysMatch(inorder, inSb.toString()) : "中序遍历不匹配，构造可能有误";
        System.out.println("✓ 验证通过\n");
    }

    private static String arrayToStr(int[] arr) {
        if (arr.length == 0) return "[]";
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            if (i > 0) sb.append(',');
            sb.append(arr[i]);
        }
        return sb.append(']').toString();
    }
}
